//003. 最大质因数
//13195 的质因数分别为 5，7，13 与 29，600851475143 最大的质因数是多少？
//答案：6857


public class week003 {
    //程序运行时间：3697300ns
//    public static boolean isPrime(long x) {
//        int end = (int) Math.sqrt(x);
//        for (int i = 2; i <= end; ++i) {
//            if (x % i == 0) {
//                return false;
//            }
//        }
//        return true;
//    }
//
//    public static void main(String[] args) {
//        long startTime = System.nanoTime();
//
//        long max = 0;
//        long num = 600851475143l;
//        long sq = (long) Math.sqrt(num);
//        for (long i = 2; i <= sq; ++i) {
//            if (num % i == 0 && isPrime(i)) {//如果当前值为目标数的质因子
//                max = Math.max(max, i);//先判断最大值
//                do {
//                    num /= i;
//                } while (num % i == 0);//将相同的质因子除去，这样可以少做很多次素数判断
//            }
//        }
//        max = Math.max(max, num);//和余数求最大值
//        System.out.println(max);
//
//        long endTime = System.nanoTime();
//        System.out.println("程序运行时间：" + (endTime - startTime) + "ns");
//    }

    //程序运行时间：148700ns
    public static void main(String[] args) {
        long num = 600851475143l;
        while (num > 2 && num % 2 == 0) num /= 2;//单独判断唯一偶质数2
        long factor = 3;
        while (factor * factor <= num) {//加速判断奇数
            //不用判断是否为质数是因为奇数的质因子已经被除干净了，例如：9
            //必须加上factor*factor<=num这个判断，示例：54
            while (factor * factor <= num && num % factor == 0) num /= factor;
            factor += 2;
        }
        System.out.println(num);
    }
}